package fun.ticsmyc.question;

/**
 * lc 878
 * @author Ticsmyc
 * @date 2021-03-09 19:35
 */
public class 神奇数字 {
    int  mod =(int)1e9+7;
    public int nthMagicalNumber(int n, int a, int b) {
        long  lcm = ((long)a)*b/gcd(a,b);

        long left =Math.min(a,b);
        long right = 200000000000000L;
        // long right= (long)Math.min(a,b) * (long)n;
        while(left < right){
            long mid = left+(right-left)/2;
            long cnt = mid/a +mid/b - mid/lcm;

            if(cnt<n){
                left= mid+1;
            }else{
                right =mid;
            }
        }
        return (int)(left%mod);
    }

    public long gcd(long a ,long b){
        if(a>b){
            long tmp =a;
            a=b;
            b=tmp;
        }
        if(a ==0) return b;
        return gcd(b%a,a);
    }
}
